package lhc.alg.top100;

import java.util.Arrays;

/**
 * description: https://leetcode.cn/problems/3sum-closest/
 *  与三数之和类似 双指针把
 *  时间复杂度 O（n^2） 空间复杂度 O（log n）
 * author: hongchen.liao
 * date:  2022/8/23
 */
public class _16_3Sum_Closest {

    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int n = nums.length;
            int best = 10000000;
            //枚举a
            for(int i = 0; i < n; i++){
                //减少枚举次数
                if(i > 0 && nums[i] == nums[i-1]){
                    continue;
                }
                //双指针枚举 b c
                int j = i+1, k = n-1;
                while(j < k){
                    int sum = nums[i] + nums[j] + nums[k];
                    if(sum == target){
                        return sum;
                    }
                    //根据绝对值的差来判断
                    if(Math.abs(sum - target) < Math.abs(best - target)){
                        best = sum;
                    }
                    //r如果大于target 移动c对应的右指针
                    if(sum > target){
                        int k0 = k-1;
                        //找到下一个不相等的
                        while(j < k0 && nums[k0] == nums[k]){
                            --k0;
                        }
                        k = k0;
                    }else{
                        //左指针类似处理
                        int j0 = j + 1;
                        while(j0 < k && nums[j0] == nums[j]){
                            ++j0;
                        }
                        j = j0;
                    }
                }

            }
            return best;
        }
    }

}
